package leetcode.tree;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Lc648 {


    public String replaceWords(List<String> dictionary, String sentence) {

        Trie trie = new Trie();
        for (String word: dictionary) {
            trie.insert(word);
        }
        String[] words = sentence.split(" ");
        for (int i = 0; i < words.length; i++) {
            String str = trie.search(words[i]);
            if (str != null)
                words[i] = str;
        }
        return String.join(" ", words);
    }

    class Trie {
        private Trie[] children ;
        private boolean isEnd;

        private String prefix;

        public Trie() {
            this.children = new Trie[26];
            this.isEnd = false;
            prefix = null;
        }

        public void insert(String word) {
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                int idx = word.charAt(i) - 'a';
                if (node.children[idx] == null)
                    node.children[idx] = new Trie();
                node = node.children[idx];
            }
            node.isEnd = true;
            node.prefix = word;
        }

        public String search(String word) {
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                int idx = word.charAt(i) - 'a';
                if (node.children[idx] == null)
                    return null;
                if (node.children[idx].isEnd) return node.children[idx].prefix;
                node = node.children[idx];
            }
            return null;
        }
    }

}
